1. Field of the Invention
This invention relates to the field of navigation of a data structure. In particular, it relates to navigation using a path expression to query a data structure.
2. Description of the Related Art
Data structures may be queried by using a path expression. There are many database systems that allow storage and querying of XML (extensible markup language) data using a path language, for example, some variation of XPath (XML Path Language). XPath is a W3C standard way of querying a tree data structure. XPath allows XML data to be queried based on path expressions. This document refers to XPath expressions and queries but should be construed as including other forms of path expressions in other path languages. A path expression is any expression that specifies a path through the hierarchical structure of an XML document. The portion of an XML document identified by a path expression is the portion that resides within the structure of the XML document at the end of any path that matches the path expression.
XML documents are often represented as document object model (DOM) structures or trees. Since path queries are evaluated by traversing these structures, a requirement of query optimization is to efficiently decrease the number of traversed nodes.
XML schema define the precise structural format of an XML document. This schema might not be available for use at runtime.
Consider a path runtime engine that does not have access to the schema of the document it is querying, only the parsed DOM tree. The authoring tool where the user enters a freeform path expression (i.e. not via a path builder) does have access to the schema.
It would be beneficial to use the descendant (//) path axis for to allow the user to find any element within the XML document by name without having to specify the full path to it. However, the descendant axis is very inefficient for the runtime engine because it needs to traverse the whole DOM tree in order to find all occurrences of this element.
“Schema-based Optimization of XPath Expression” by April Kwong and Michael Gertz, Department of Computer Science, University of California at Davis discloses optimization of XPath Expressions using path equivalent classes generated from a schema. The optimization method includes the expansion of wildcards in XPath expressions.